package leetcode.code0241;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public List<Integer> diffWaysToCompute(String expression) {
		Integer[] exp = this.str2array(expression);
		int len = exp.length;
		Map<String, List<Integer>> hash = new HashMap<>();
		return this.f(exp, 1, len - 2, hash);
	}

	private List<Integer> f(Integer[] exp, int start, int end, Map<String, List<Integer>> hash) {
		String key = start + "_" + end;
		List<Integer> ans = hash.getOrDefault(key, new ArrayList<>());
		if (ans.size() > 0) {
			return ans;
		}
		if (start > end) {
			ans.add(exp[start - 1]);
			hash.put(key, ans);
			return ans;
		}
		if (start == end) {
			ans.add(this.cal(exp[start - 1], exp[start], exp[start + 1]));
			hash.put(key, ans);
			return ans;
		}
		for (int i = start; i <= end; i += 2) {
			List<Integer> left = this.f(exp, start, i - 2, hash);
			List<Integer> right = this.f(exp, i + 2, end, hash);
			for (int l = 0; l < left.size(); l++) {
				for (int r = 0; r < right.size(); r++) {
					ans.add(this.cal(left.get(l), exp[i], right.get(r)));
				}
			}
		}
		return ans;
	}

	private Integer cal(Integer num1, Integer op, Integer num2) {
		if (op == 0) {
			return num1 + num2;
		} else if (op == 1) {
			return num1 - num2;
		}
		return num1 * num2;
	}

	private Integer[] str2array(String expression) {
		List<Integer> list = new ArrayList<>();
		char[] exp = expression.toCharArray();
		int len = expression.length();
		int p = 0;
		int num = 0;
		while (p < len) {
			char c = exp[p];
			if (c == '+') {
				list.add(num);
				list.add(0);
				num = 0;
			} else if (c == '-') {
				list.add(num);
				list.add(1);
				num = 0;
			} else if (c == '*') {
				list.add(num);
				list.add(2);
				num = 0;
			} else {
				num = num * 10 + c - '0';
			}
			p++;
		}
		list.add(num);
		return list.toArray(new Integer[list.size()]);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//
//		System.out.println((int) '+');
//		System.out.println((int) '-');
//		System.out.println((int) '*');
	}

	@Override
	public void debug1() {
		List<Integer> e = HelpDebug.str2intlist("[-34, -14, -10, -10, 10]");
		HelpDebug.compare(e, this.diffWaysToCompute("2*3-4*5"));

	}

	@Override
	public void debug2() {
		List<Integer> e = HelpDebug.str2intlist("[0, 2]");
		HelpDebug.compare(e, this.diffWaysToCompute("2-1-1"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		List<Integer> e = HelpDebug.str2intlist("[8,8,8,8,8]");
		HelpDebug.compare(e, this.diffWaysToCompute("2+2+2+2"));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

}
